package online.hxstart.code.easy;

import java.util.Arrays;

/**
 * @author huxing
 * @date 19-2-20 星期三 下午2:21
 * @describe 8种排序方法
 */
public class EightMethodsShort {

    /**
     * 排序前准备数组
     */
    private int[] array = {1, 3, 5, 8, 321, 312, 31, 34, 5, 1, 6, 7, 8, 9, 12};

    public static void main(String[] args) {
        EightMethodsShort methodsShort = new EightMethodsShort();
        BubbleSort.bubble(methodsShort.array);
        QuickSort.quick(methodsShort.array);
        InsertSort.insert(methodsShort.array);
        ChooseSort.choose(methodsShort.array);
        ShellSort.shell(methodsShort.array);
    }

    /**
     * 冒泡排序
     */
    private static class BubbleSort {

        /**
         * @describe 冒泡排序, 比较相邻的元素。如果第一个比第二个大，就交换他们两个。直到没有任何一对数字需要比较。
         */
        private static void bubble(int[] a) {
            int tem;
            for (int i = 0; i < a.length - 1; i++) {
                for (int j = 0; j < a.length - i - 1; j++) {
                    if (a[j] > a[j + 1]) {
                        tem = a[j];
                        a[j] = a[j + 1];
                        a[j + 1] = tem;
                    }
                }
            }
            System.out.println("冒泡排序： " + Arrays.toString(a));
        }
    }

    /**
     * 快速排序法
     */
    private static class QuickSort {

        private static int[] quickSort(int[] a, int start, int end) {
            if (start < end) {
                //初始中间数位于数组首位
                int temp = a[start];
                int tempStart = start, tempEnd = end;
                while (start < end) {
                    //当末尾数大于中间数
                    while (start < end && a[end] >= temp) {
                        //比较
                        end--;
                    }
                    a[start] = a[end];
                    while (start < end && a[start] <= temp) {
                        start++;
                    }
                    a[end] = a[start];
                }
                a[start] = temp;

                int center = start;
                a = quickSort(a, tempStart, center - 1);
                return quickSort(a, center + 1, tempEnd);
            }
            return a;
        }

        static void quick(int[] a) {
            a = quickSort(a, 0, a.length - 1);
            System.out.println("快速排序： " + Arrays.toString(a));
        }
    }

    /**
     * 插入排序
     */
    private static class InsertSort {

        static void insert(int[] a) {
            int temp, j;
            for (int i = 1; i < a.length; i++) {
                temp = a[i];
                j = i;
                while (j > 0 && temp < a[j - 1]) {
                    a[j] = a[j - 1];
                    j--;
                }
                a[j] = temp;
            }
            System.out.println("插入排序： " + Arrays.toString(a));
        }
    }

    /**
     * 选择排序法
     */
    private static class ChooseSort {

        static void choose(int[] a) {
            int temp, tempJ;
            for (int i = 0; i < a.length; i++) {
                tempJ = i;
                temp = a[i];
                for (int j = i + 1; j < a.length; j++) {
                    if (a[j] < temp) {
                        tempJ = j;
                    }
                }
                a[i] = a[tempJ];
                a[tempJ] = temp;
            }
            System.out.println("选择排序： " + Arrays.toString(a));
        }
    }

    private static class ShellSort {

        static int[] shell(int[] a) {
            int type = 2, temp;
            for (int i = a.length / type; i > 0; i /= type) {
                for (int j = i; j < a.length; j++) {
                    temp = a[j];
                    for (int k = j; k > i; k -= i) {
                        if (temp > a[k - i]) {
                            a[k] = a[k - i];
                        } else {
                            break;
                        }
                        a[k] = temp;
                    }
                }
            }
            System.out.println("希尔排序： " + Arrays.toString(a));
            return a;
        }
    }
}
